package leetcode_动态规划._07背包问题._01背包;

/**
 * @author yzh
 * @data 2021/3/18 17:41
 * 一和零
 * 在数组中找到一个子集，这个子集中 0 的个数和 1 的个数分别不能超过 m 和 n
 * 并且这个子集要是最大的
 * 思路：
 *   dp[i][j] 表示最大 i 个 0 和最大 j 个 1 的最大子集
 *   dp[i][j] = max(dp[i][j], dp[i - [0]][j - [1]] + 1)
 */
public class _474 {

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int ans = 0;
        for (String str : strs) {
            int[] count = count(str);
            for (int i = m; i >= count[0]; --i) {
                for (int j = n; j >= count[1]; --j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - count[0]][j - count[1]] + 1);
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
    public int[] count(String str) {
        int[] res = new int[2];
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') {
                ++res[0];
            } else {
                ++res[1];
            }
        }
        return res;
    }
}
